﻿using System;
using System.Collections.Generic;
using GeoAPI.Geometries;
using NetTopologySuite.Geometries;
using NetTopologySuite.IO;
using NetTopologySuite.Utilities;

namespace NetTopologySuite.Triangulate.QuadEdge
{
	public class QuadEdgeSubdivision
	{
		public static void GetTriangleEdges(QuadEdge startQE, QuadEdge[] triEdge)
		{
			triEdge[0] = startQE;
			triEdge[1] = triEdge[0].LNext;
			triEdge[2] = triEdge[1].LNext;
			if (triEdge[2].LNext != triEdge[0])
			{
				throw new ArgumentException("Edges do not form a triangle");
			}
		}

		public QuadEdgeSubdivision(Envelope env, double tolerance)
		{
			this._tolerance = tolerance;
			this._edgeCoincidenceTolerance = tolerance / 1000.0;
			this.CreateFrame(env);
			this._startingEdge = this.InitSubdiv();
			this._locator = new LastFoundQuadEdgeLocator(this);
		}

		private void CreateFrame(Envelope env)
		{
			double width = env.Width;
			double height = env.Height;
			double num;
			if (width > height)
			{
				num = width * 10.0;
			}
			else
			{
				num = height * 10.0;
			}
			this._frameVertex[0] = new Vertex((env.MaxX + env.MinX) / 2.0, env.MaxY + num);
			this._frameVertex[1] = new Vertex(env.MinX - num, env.MinY - num);
			this._frameVertex[2] = new Vertex(env.MaxX + num, env.MinY - num);
			this._frameEnv = new Envelope(this._frameVertex[0].Coordinate, this._frameVertex[1].Coordinate);
			this._frameEnv.ExpandToInclude(this._frameVertex[2].Coordinate);
		}

		private QuadEdge InitSubdiv()
		{
			QuadEdge quadEdge = this.MakeEdge(this._frameVertex[0], this._frameVertex[1]);
			QuadEdge quadEdge2 = this.MakeEdge(this._frameVertex[1], this._frameVertex[2]);
			QuadEdge.Splice(quadEdge.Sym, quadEdge2);
			QuadEdge quadEdge3 = this.MakeEdge(this._frameVertex[2], this._frameVertex[0]);
			QuadEdge.Splice(quadEdge2.Sym, quadEdge3);
			QuadEdge.Splice(quadEdge3.Sym, quadEdge);
			return quadEdge;
		}

		public double Tolerance
		{
			get
			{
				return this._tolerance;
			}
		}

		public Envelope Envelope
		{
			get
			{
				return new Envelope(this._frameEnv);
			}
		}

		public IList<QuadEdge> GetEdges()
		{
			return this._quadEdges;
		}

		public void SetLocator(IQuadEdgeLocator locator)
		{
			this._locator = locator;
		}

		public QuadEdge MakeEdge(Vertex o, Vertex d)
		{
			QuadEdge quadEdge = QuadEdge.MakeEdge(o, d);
			this._quadEdges.Add(quadEdge);
			return quadEdge;
		}

		public QuadEdge Connect(QuadEdge a, QuadEdge b)
		{
			QuadEdge quadEdge = QuadEdge.Connect(a, b);
			this._quadEdges.Add(quadEdge);
			return quadEdge;
		}

		public void Delete(QuadEdge e)
		{
			QuadEdge.Splice(e, e.OPrev);
			QuadEdge.Splice(e.Sym, e.Sym.OPrev);
			QuadEdge sym = e.Sym;
			QuadEdge rot = e.Rot;
			QuadEdge sym2 = e.Rot.Sym;
			this._quadEdges.Remove(e);
			this._quadEdges.Remove(sym);
			this._quadEdges.Remove(rot);
			this._quadEdges.Remove(sym2);
			e.Delete();
			sym.Delete();
			rot.Delete();
			sym2.Delete();
		}

		public QuadEdge LocateFromEdge(Vertex v, QuadEdge startEdge)
		{
			int num = 0;
			int count = this._quadEdges.Count;
			QuadEdge quadEdge = startEdge;
			for (;;)
			{
				num++;
				if (num > count)
				{
					break;
				}
				if (v.Equals(quadEdge.Orig) || v.Equals(quadEdge.Dest))
				{
					return quadEdge;
				}
				if (v.RightOf(quadEdge))
				{
					quadEdge = quadEdge.Sym;
				}
				else if (!v.RightOf(quadEdge.ONext))
				{
					quadEdge = quadEdge.ONext;
				}
				else
				{
					if (v.RightOf(quadEdge.DPrev))
					{
						return quadEdge;
					}
					quadEdge = quadEdge.DPrev;
				}
			}
			throw new LocateFailureException(quadEdge.ToLineSegment());
		}

		public QuadEdge Locate(Vertex v)
		{
			return this._locator.Locate(v);
		}

		public QuadEdge Locate(Coordinate p)
		{
			return this._locator.Locate(new Vertex(p));
		}

		public QuadEdge Locate(Coordinate p0, Coordinate p1)
		{
			QuadEdge quadEdge = this._locator.Locate(new Vertex(p0));
			if (quadEdge == null)
			{
				return null;
			}
			QuadEdge quadEdge2 = quadEdge;
			if (quadEdge.Dest.Coordinate.Equals2D(p0))
			{
				quadEdge2 = quadEdge.Sym;
			}
			QuadEdge quadEdge3 = quadEdge2;
			while (!quadEdge3.Dest.Coordinate.Equals2D(p1))
			{
				quadEdge3 = quadEdge3.ONext;
				if (quadEdge3 == quadEdge2)
				{
					return null;
				}
			}
			return quadEdge3;
		}

		public QuadEdge InsertSite(Vertex v)
		{
			QuadEdge quadEdge = this.Locate(v);
			if (v.Equals(quadEdge.Orig, this._tolerance) || v.Equals(quadEdge.Dest, this._tolerance))
			{
				return quadEdge;
			}
			QuadEdge quadEdge2 = this.MakeEdge(quadEdge.Orig, v);
			QuadEdge.Splice(quadEdge2, quadEdge);
			QuadEdge quadEdge3 = quadEdge2;
			do
			{
				quadEdge2 = this.Connect(quadEdge, quadEdge2.Sym);
				quadEdge = quadEdge2.OPrev;
			}
			while (quadEdge.LNext != quadEdge3);
			return quadEdge3;
		}

		public bool IsFrameEdge(QuadEdge e)
		{
			return this.IsFrameVertex(e.Orig) || this.IsFrameVertex(e.Dest);
		}

		public bool IsFrameBorderEdge(QuadEdge e)
		{
			QuadEdge[] triEdge = new QuadEdge[3];
			QuadEdgeSubdivision.GetTriangleEdges(e, triEdge);
			QuadEdge[] triEdge2 = new QuadEdge[3];
			QuadEdgeSubdivision.GetTriangleEdges(e.Sym, triEdge2);
			Vertex dest = e.LNext.Dest;
			if (this.IsFrameVertex(dest))
			{
				return true;
			}
			Vertex dest2 = e.Sym.LNext.Dest;
			return this.IsFrameVertex(dest2);
		}

		public bool IsFrameVertex(Vertex v)
		{
			return v.Equals(this._frameVertex[0]) || v.Equals(this._frameVertex[1]) || v.Equals(this._frameVertex[2]);
		}

		public bool IsOnEdge(QuadEdge e, Coordinate p)
		{
			this.seg.SetCoordinates(e.Orig.Coordinate, e.Dest.Coordinate);
			return this.seg.Distance(p) < this._edgeCoincidenceTolerance;
		}

		public bool IsVertexOfEdge(QuadEdge e, Vertex v)
		{
			return v.Equals(e.Orig, this._tolerance) || v.Equals(e.Dest, this._tolerance);
		}

		public IEnumerable<Vertex> GetVertices(bool includeFrame)
		{
			HashSet<Vertex> hashSet = new HashSet<Vertex>();
			foreach (QuadEdge quadEdge in this._quadEdges)
			{
				Vertex orig = quadEdge.Orig;
				if (includeFrame || !this.IsFrameVertex(orig))
				{
					hashSet.Add(orig);
				}
				Vertex dest = quadEdge.Dest;
				if (includeFrame || !this.IsFrameVertex(dest))
				{
					hashSet.Add(dest);
				}
			}
			return hashSet;
		}

		public IList<QuadEdge> GetVertexUniqueEdges(bool includeFrame)
		{
			List<QuadEdge> list = new List<QuadEdge>();
			HashSet<Vertex> hashSet = new HashSet<Vertex>();
			foreach (QuadEdge quadEdge in this._quadEdges)
			{
				Vertex orig = quadEdge.Orig;
				if (!hashSet.Contains(orig))
				{
					hashSet.Add(orig);
					if (includeFrame || !this.IsFrameVertex(orig))
					{
						list.Add(quadEdge);
					}
				}
				QuadEdge sym = quadEdge.Sym;
				Vertex orig2 = sym.Orig;
				if (!hashSet.Contains(orig2))
				{
					hashSet.Add(orig2);
					if (includeFrame || !this.IsFrameVertex(orig2))
					{
						list.Add(sym);
					}
				}
			}
			return list;
		}

		public IList<QuadEdge> GetPrimaryEdges(bool includeFrame)
		{
			this._visitedKey++;
			List<QuadEdge> list = new List<QuadEdge>();
			Stack<QuadEdge> stack = new Stack<QuadEdge>();
			stack.Push(this._startingEdge);
			HashSet<QuadEdge> hashSet = new HashSet<QuadEdge>();
			while (stack.Count > 0)
			{
				QuadEdge quadEdge = stack.Pop();
				if (!hashSet.Contains(quadEdge))
				{
					QuadEdge primary = quadEdge.GetPrimary();
					if (includeFrame || !this.IsFrameEdge(primary))
					{
						list.Add(primary);
					}
					stack.Push(quadEdge.ONext);
					stack.Push(quadEdge.Sym.ONext);
					hashSet.Add(quadEdge);
					hashSet.Add(quadEdge.Sym);
				}
			}
			return list;
		}

		public void VisitTriangles(ITriangleVisitor triVisitor, bool includeFrame)
		{
			this._visitedKey++;
			Stack<QuadEdge> stack = new Stack<QuadEdge>();
			stack.Push(this._startingEdge);
			HashSet<QuadEdge> hashSet = new HashSet<QuadEdge>();
			while (stack.Count > 0)
			{
				QuadEdge quadEdge = stack.Pop();
				if (!hashSet.Contains(quadEdge))
				{
					QuadEdge[] array = this.FetchTriangleToVisit(quadEdge, stack, includeFrame, hashSet);
					if (array != null)
					{
						triVisitor.Visit(array);
					}
				}
			}
		}

		private QuadEdge[] FetchTriangleToVisit(QuadEdge edge, Stack<QuadEdge> edgeStack, bool includeFrame, HashSet<QuadEdge> visitedEdges)
		{
			QuadEdge quadEdge = edge;
			int num = 0;
			bool flag = false;
			do
			{
				this._triEdges[num] = quadEdge;
				if (this.IsFrameEdge(quadEdge))
				{
					flag = true;
				}
				QuadEdge sym = quadEdge.Sym;
				if (!visitedEdges.Contains(sym))
				{
					edgeStack.Push(sym);
				}
				visitedEdges.Add(quadEdge);
				num++;
				quadEdge = quadEdge.LNext;
			}
			while (quadEdge != edge);
			if (flag && !includeFrame)
			{
				return null;
			}
			return this._triEdges;
		}

		public IList<QuadEdge[]> GetTriangleEdges(bool includeFrame)
		{
			QuadEdgeSubdivision.TriangleEdgesListVisitor triangleEdgesListVisitor = new QuadEdgeSubdivision.TriangleEdgesListVisitor();
			this.VisitTriangles(triangleEdgesListVisitor, includeFrame);
			return triangleEdgesListVisitor.GetTriangleEdges();
		}

		public IList<Vertex[]> GetTriangleVertices(bool includeFrame)
		{
			QuadEdgeSubdivision.TriangleVertexListVisitor triangleVertexListVisitor = new QuadEdgeSubdivision.TriangleVertexListVisitor();
			this.VisitTriangles(triangleVertexListVisitor, includeFrame);
			return triangleVertexListVisitor.GetTriangleVertices();
		}

		public IList<Coordinate[]> GetTriangleCoordinates(bool includeFrame)
		{
			QuadEdgeSubdivision.TriangleCoordinatesVisitor triangleCoordinatesVisitor = new QuadEdgeSubdivision.TriangleCoordinatesVisitor();
			this.VisitTriangles(triangleCoordinatesVisitor, includeFrame);
			return triangleCoordinatesVisitor.GetTriangles();
		}

		public IMultiLineString GetEdges(IGeometryFactory geomFact)
		{
			IList<QuadEdge> primaryEdges = this.GetPrimaryEdges(false);
			ILineString[] array = new LineString[primaryEdges.Count];
			int num = 0;
			foreach (QuadEdge quadEdge in primaryEdges)
			{
				array[num++] = geomFact.CreateLineString(new Coordinate[]
				{
					quadEdge.Orig.Coordinate,
					quadEdge.Dest.Coordinate
				});
			}
			return geomFact.CreateMultiLineString(array);
		}

		public IGeometryCollection GetTriangles(IGeometryFactory geomFact)
		{
			IList<Coordinate[]> triangleCoordinates = this.GetTriangleCoordinates(false);
			IPolygon[] array = new Polygon[triangleCoordinates.Count];
			int num = 0;
			foreach (Coordinate[] coordinates in triangleCoordinates)
			{
				array[num++] = geomFact.CreatePolygon(geomFact.CreateLinearRing(coordinates), null);
			}
			return geomFact.CreateGeometryCollection(array);
		}

		public IGeometryCollection GetVoronoiDiagram(IGeometryFactory geomFact)
		{
			IList<IGeometry> voronoiCellPolygons = this.GetVoronoiCellPolygons(geomFact);
			return geomFact.CreateGeometryCollection(GeometryFactory.ToGeometryArray(voronoiCellPolygons));
		}

		public IList<IGeometry> GetVoronoiCellPolygons(IGeometryFactory geomFact)
		{
			this.VisitTriangles(new QuadEdgeSubdivision.TriangleCircumcentreVisitor(), true);
			List<IGeometry> list = new List<IGeometry>();
			foreach (QuadEdge qe in this.GetVertexUniqueEdges(false))
			{
				list.Add(this.GetVoronoiCellPolygon(qe, geomFact));
			}
			return list;
		}

		public IPolygon GetVoronoiCellPolygon(QuadEdge qe, IGeometryFactory geomFact)
		{
			List<Coordinate> list = new List<Coordinate>();
			QuadEdge quadEdge = qe;
			do
			{
				Coordinate coordinate = qe.Rot.Orig.Coordinate;
				list.Add(coordinate);
				qe = qe.OPrev;
			}
			while (qe != quadEdge);
			CoordinateList coordinateList = new CoordinateList();
			coordinateList.AddAll(list, false);
			coordinateList.CloseRing();
			if (coordinateList.Count < 4)
			{
				coordinateList.Add(coordinateList[coordinateList.Count - 1], true);
			}
			Coordinate[] coordinates = coordinateList.ToCoordinateArray();
			IPolygon polygon = geomFact.CreatePolygon(geomFact.CreateLinearRing(coordinates), null);
			Vertex orig = quadEdge.Orig;
			polygon.UserData = orig.Coordinate;
			return polygon;
		}

		private const double EdgeCoincidenceToleranceFactor = 1000.0;

		private int _visitedKey;

		private readonly List<QuadEdge> _quadEdges = new List<QuadEdge>();

		private readonly QuadEdge _startingEdge;

		private readonly double _tolerance;

		private readonly double _edgeCoincidenceTolerance;

		private readonly Vertex[] _frameVertex = new Vertex[3];

		private Envelope _frameEnv;

		private IQuadEdgeLocator _locator;

		private readonly LineSegment seg = new LineSegment();

		private readonly QuadEdge[] _triEdges = new QuadEdge[3];

		private class TriangleCircumcentreVisitor : ITriangleVisitor
		{
			public void Visit(QuadEdge[] triEdges)
			{
				Coordinate coordinate = triEdges[0].Orig.Coordinate;
				Coordinate coordinate2 = triEdges[1].Orig.Coordinate;
				Coordinate coordinate3 = triEdges[2].Orig.Coordinate;
				Vertex orig = new Vertex(Triangle.Circumcentre(coordinate, coordinate2, coordinate3));
				for (int i = 0; i < 3; i++)
				{
					triEdges[i].Rot.Orig = orig;
				}
			}
		}

		private class TriangleEdgesListVisitor : ITriangleVisitor
		{
			public void Visit(QuadEdge[] triEdges)
			{
				this._triList.Add((QuadEdge[])triEdges.Clone());
			}

			public IList<QuadEdge[]> GetTriangleEdges()
			{
				return this._triList;
			}

			private readonly IList<QuadEdge[]> _triList = new List<QuadEdge[]>();
		}

		private class TriangleVertexListVisitor : ITriangleVisitor
		{
			public void Visit(QuadEdge[] triEdges)
			{
				this._triList.Add(new Vertex[]
				{
					triEdges[0].Orig,
					triEdges[1].Orig,
					triEdges[2].Orig
				});
			}

			public IList<Vertex[]> GetTriangleVertices()
			{
				return this._triList;
			}

			private readonly IList<Vertex[]> _triList = new List<Vertex[]>();
		}

		private class TriangleCoordinatesVisitor : ITriangleVisitor
		{
			public void Visit(QuadEdge[] triEdges)
			{
				this._coordList.Clear();
				for (int i = 0; i < 3; i++)
				{
					Vertex orig = triEdges[i].Orig;
					this._coordList.Add(orig.Coordinate);
				}
				if (this._coordList.Count > 0)
				{
					this._coordList.CloseRing();
					Coordinate[] array = this._coordList.ToCoordinateArray();
					if (array.Length != 4)
					{
						return;
					}
					this._triCoords.Add(array);
				}
			}

			private static void CheckTriangleSize(Coordinate[] pts)
			{
				string str = "";
				if (pts.Length >= 2)
				{
					str = WKTWriter.ToLineString(pts[0], pts[1]);
				}
				else if (pts.Length >= 1)
				{
					str = WKTWriter.ToPoint(pts[0]);
				}
				Assert.IsTrue(pts.Length == 4, "Too few points for visited triangle at " + str);
			}

			public IList<Coordinate[]> GetTriangles()
			{
				return this._triCoords;
			}

			private readonly CoordinateList _coordList = new CoordinateList();

			private readonly List<Coordinate[]> _triCoords = new List<Coordinate[]>();
		}
	}
}
